class Solution1 {
    public boolean isMatch(String ss, String pp) {
        int n = ss.length(), m = pp.length();
        ss = " " + ss;
        pp = " " + pp;
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        boolean[][] dp = new boolean[n+1][m+1];

        dp[0][0] = true;
        for(int i = 2; i<= m; i+=2) {
            if(p[i] == '*') {
                dp[0][i] = true;
            }else {
                break;
            }
        }

        for(int i = 1; i<=n; i++) {
            for(int j = 1; j<=m; j++) {
                if(s[i] == p[j] || p[j] == '.') {
                    dp[i][j] = dp[i-1][j-1];
                }else if(p[j] == '*') {
                    if(p[j-1] == '.') {
                        dp[i][j] = dp[i][j-2] || dp[i-1][j];
                    }else {
                        dp[i][j] = dp[i][j-2] || (s[i] == p[j-1] && dp[i-1][j]);
                    }
                }
                //System.out.print(dp[i][j]+ " ");
            }
            //System.out.println();
        }

        return dp[n][m];
    }
}


class Solution {
    public boolean isInterleave(String ss1, String ss2, String ss3) {
        int n = ss1.length(), m = ss2.length();
        boolean[][] dp = new boolean[n+1][m+1];
        char[] s1 = ss1.toCharArray();
        char[] s2 = ss2.toCharArray();
        char[] s3 = ss3.toCharArray();

        for(int i = 1; i<=m; i++) {
            if(s3[i] == s2[i]) dp[0][i] = true;
            else break;
        }
        for(int i = 1; i<=n; i++) {
            if(s3[i] == s1[i]) dp[i][0] = true;
            else break;
        }

        for(int i = 1; i<=n; i++) {
            for(int j = 1; j<=m; j++) {
                if(s1[i] == s3[i+j]) {
                    dp[i][j] = dp[i-1][j];
                }
                if(s2[j] == s3[i+j]) {
                    dp[i][j] = dp[i][j-1];
                }
            }
        }

        return dp[n][m];
    }
}

public class Test {
}
